const t1 = new Date(); // 开始时间记录
var quickSort = function (arr) {
  if (arr.length <= 1) { return arr; }
  var pivotIndex = Math.floor(arr.length / 2);
  var pivot = arr.splice(pivotIndex, 1)[0];
  var left = [];
  var right = [];
  for (var i = 0; i < arr.length; i++) {
    if (arr[i] < pivot) {
      left.push(arr[i]);
    } else {
      right.push(arr[i]);
    }
  }
  return quickSort(left).concat([pivot], quickSort(right));
};
const { randomArr } = require('../createArr')
const result = quickSort(randomArr)
const t2 = new Date(); // 结束时间记录
console.log('用时' + (t2 - t1) + '毫秒' + '\n', result)

// ** 阮一峰版
// 原理  核心思想 “参照-划分-递归”
// 1、选择数组中间数作为基数，并从数组中取出此基数；
// 2、准备两个数组容器，遍历数组，逐个与基数比对，较小的放左边容器，较大的放右边容器；
// 3、递归处理两个容器的元素，并将处理后的数据与基数按大小合并成一个数组，返回。

// 问题::
// 1、R取基数用的是splice()函数取，而不是算法中常用的取下标。基数只是一个参照对象，在比对的时候，
// 只要能从数组中取到即可，所以只需要知道它的索引即可，调用函数删除基数只会更耗时；
// 2、根据基数来划分时，R专门生成两个数组来存储，从而占用了更多的存储空间（增加了空间复杂度）。
// 严格上讲，R的代码仅仅是用快速排序的思想实现了排序，也算是快速排序，但是还有很多改进之处。

// 不稳定排序